You're given a square matrix of integers matrix of size n × n.

Let's define a bouncing diagonal as a sequence which starts from a cell of the leftmost column, and continues diagonally (up-right) until it reaches the rightmost column, bouncing vertically if it reaches the top of the matrix.

For each cell of the leftmost column, let's define its weight as the sum of the elements in the bouncing diagonals starting from that cell.

Your task is to sort the elements of the leftmost column by their weights in ascending order. In case of a tie, sort them by their values, also in ascending order.

Return the sorted values of the leftmost column of matrix as a single array.

Example

• For

  matrix = [[2, 3, 2],
            [0, 2, 5],
            [1, 0, 1]]
  

  the output should be bouncingDiagonals(matrix) = [1, 2, 0].

  

  • The weight of the first element is 2 + 2 + 1 = 5
  • The weight of the second element is 0 + 3 + 5 = 8
  • The weight of the third element is 1 + 2 + 2 = 5

  The second element weight is greater than the others, so its value (0) goes to the end of the resulting array. There's a tie between the first and third elements, so they must be sorted by their values (1, 2). Therefore, the final order of the elements in the leftmost column is [1, 2, 0].

• For

  matrix = [[1, 3, 2, 5],
            [3, 2, 5, 0],
            [9, 0, 1, 3],
            [6, 1, 0, 8]]
  

  the output should be bouncingDiagonals(matrix) = [1, 9, 3, 6].

  

  • The weight of the first element is 1 + 2 + 1 + 8 = 12
  • The weight of the second element is 3 + 3 + 5 + 3 = 14
  • The weight of the third element is 9 + 2 + 2 + 0 = 13
  • The weight of the fourth element is 6 + 0 + 5 + 5 = 16

  Each of the weights are different in this case, and their ascending order is first, third, second, and fourth. So the final order of the elements in the leftmost column is [1, 9, 3, 6].

Input/Output

• [execution time limit] 3 seconds (java)

• [input] array.array.integer matrix

  A matrix of integers.

  Guaranteed constraints:
  2 ≤ matrix.length ≤ 500,
  matrix[i].length = matrix.length,
  0 ≤ matrix[i][j] ≤ 1000.

• [output] array.integer

  An array containing the values of the leftmost column of matrix, sorted by their weights.

[Java] Syntax Tips

// Prints help message to the console
// Returns a string
// 
// Globals declared here will cause a compilation error,
// declare variables inside the function instead!
String helloWorld(String name) {
    System.out.println("This prints to the console when you Run Tests");
    return "Hello, " + name;
}